package com.nanbei.dp;

import java.util.Arrays;
import java.util.stream.IntStream;

/**
 * @ClassDescription: 动态规划 （0-1背包问题） 给定一组物品，每个物品有重量和价值，在限制总重量的前提下，选择某些物品使总价值最大化。
 * @JdkVersion: 1.8
 * @Author: libs
 * @Created: 2024/7/5 16:42
 */
public class KnapsackProblem {
    /*
        1. n个物品都是固体，有重量和价值
        2. 现在你要取走不超过 10克 的物品
        3. 每次可以不拿或全拿，问最高价值是多少

            编号 重量(g)  价值(元)                        简称
            1   4       1600           黄金一块   400    A
            2   8       2400           红宝石一粒 300    R
            3   5       30             白银一块         S
            0   1       1_000_000      钻石一粒          D
        1_001_630

        1_002_400
     */

    /*
        1   2   3   4   5   6   7   8   9   10
                    a
                    a               r
                    a               r
        d               da          da  dr  dr
     */

    static class Item {
        int index;
        String name;
        int weight;
        int value;

        public Item(int index, String name, int weight, int value) {
            this.index = index;
            this.name = name;
            this.weight = weight;
            this.value = value;
        }

        @Override
        public String toString() {
            return "Item(" + name + ")";
        }
    }

    public static void main(String[] args) {
        Item[] items = new Item[]{
                new Item(1, "黄金", 4, 1600),
                new Item(2, "宝石", 8, 2400),
                new Item(3, "白银", 5, 30),
                new Item(4, "钻石", 1, 10_000),
        };
        System.out.println(select(items, 10));
        System.out.println(select2(items, 10));
    }


    /**
     * 0-1 背包问题 和 完全背包问题最大的不同是：
     *        0-1 背包问题的物品只能存放一次 而 完全背包问题的物品可以无限次的取出
     *        所以 0-1 在获取最大价值的时候只能去 dp[i-1][j- item.weight] 处去获取
     *        而 完全背包  则是在 dp[i][j- item.weight] 处去获取
     */
    private static int select(Item[] items, int total) {
        int length = items.length;
        int[][] dp = new int[length][total+1];
        //初始化第一行数据
        for (int i = 0; i < total+1; i++) {
            Item item = items[0];
            if (i>=item.weight ){
                dp[0][i] = item.value;
            }
        }
        print(dp);

        for (int i = 1; i < length; i++) {
            Item item = items[i];
            for (int j = 0; j < total+1; j++) {
                if (j>=item.weight ){
                    // j-item.weight: 当前背包容量-这次物品重量=剩余背包空间
                    // dp[i-1][j- item.weight]+item.value: 剩余背包空间能装下的最大价值 + 这次物品价值
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j- item.weight]+item.value);
                }else {
                    dp[i][j] = dp[i-1][j];
                }
            }
            print(dp);
        }
        return dp[length-1][total];
    }

    // 二维数组降维至一维数组
    private static int select2(Item[] items, int total) {
        int length = items.length;
        int[] dp = new int[total+1];
        //初始化第一行数据

        for (int i = 0; i < length; i++) {
            Item item = items[i];
            // 因为在计算的过程中我们需要用到上一次数组的计算的数据 所以我们从前向后走
            for (int j = total; j >0; j--) {
                if (j>=item.weight ){
                    // j-item.weight: 当前背包容量-这次物品重量=剩余背包空间
                    // dp[i-1][j- item.weight]+item.value: 剩余背包空间能装下的最大价值 + 这次物品价值
                    dp[j] = Math.max(dp[j], dp[j- item.weight]+item.value);
                }
            }
            System.out.println(Arrays.toString(dp));
        }
        return dp[total];
    }






    //  打印数组的方法
    static void print(int[][] dp) {
        // 使用 StringBuilder 构造分隔线
        StringBuilder separator = new StringBuilder("   ");
        for (int i = 0; i < 63; i++) {
            separator.append("-");
        }
        System.out.println(separator);

        // 打印列的索引
        Object[] array = IntStream.range(0, dp[0].length).boxed().toArray();
        printArray(array);

        // 打印每行数据
        for (int[] d : dp) {
            array = Arrays.stream(d).boxed().toArray();
            printArray(array);
        }
    }

    private static void printArray(Object[] array) {
        for (Object obj : array) {
            System.out.printf("%5d ", obj);
        }
        System.out.println();
    }
}
